package com.example.leetcode.leetcode.hot100;

import com.example.leetcode.leetcode.tree.TreeNode;

/**
 * @author haitao
 * @date 2021/7/28 3:34 下午
 *
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 *           1
 *          / \
 *         2   3
 *        / \
 *       4   5
 */
public class Solution543 {
    int maxlength = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return 0;
    }

    public int depth(TreeNode root){

        if (root == null){
            return 0;
        }
        // DFS求左子树最大深度
        int l = depth(root.left);
        int r = depth(root.right);
        // 最大长度为当前节点左子树深度+右子树深度的和
        maxlength = Math.max(l+r,maxlength);

        return Math.max(l,r)+1;
    }

    public static void main(String[] args) {
        Solution543 solution543 = new Solution543();
    }
}
